package com.zang.tree;

/**
 * @author ZVerify
 * @since 2022/11/02 15:01
 * @see <a href="https://leetcode.cn/problems/delete-node-in-a-bst/">...</a>
 **/
public class 删除二叉搜索树中的节点 {
    public TreeNode deleteNode(TreeNode root, int key) {

        return dfs(root,key);
    }

    private TreeNode dfs(TreeNode root, int key) {
       if (root==null) return null;
       // 搜索树的特性
       if (root.val<key) {
           root.right = dfs(root.right, key);
       } else if (root.val>key) {
           root.left = dfs(root.left, key);
       }else {
           // 现在已经找到了，拿到当前的节点左右节点
           TreeNode left = root.left;
           TreeNode right = root.right;
           // 如果右节点为null则直接返回左节点给上一节点当子节点
           if (right == null) return left;
           // 如果当前节点存在右节点找到有节点为根节点树的最左节点把左节点放到他左边
           while (right!=null && right.left!=null){
               right = right.left;
           }
           right.left = left;
           // 完成操作后返回左节点
           return right;
       }
       // 删除完之后返回当前节点给上一节点
       return root;
    }
}
